package learn.link;

import learn.CommUtil;

/**
 * 判断是否是回文结构
 */
public class IsPalindromeList {

    public static void main(String[] args) {
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(4);
        head1.next.next.next.next.next = new Node(3);
        head1.next.next.next.next.next.next = new Node(2);
        head1.next.next.next.next.next.next.next = new Node(1);
        CommUtil.printLinkedList(head1);
        System.out.println(isPalindrome(head1));
        CommUtil.printLinkedList(head1);
    }

    /**
     * 判断是否是回文结构
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(Node head) {


        if (head == null) {
            return true;
        }
        //找到中间节点
        Node slow = head;//slow 就是中间节点
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 1→2→3←2←1
        //     ↓
        //    null
        //或者
        // 1→2→3←3←2←1
        //     ↓
        //    null
        Node n1 = slow.next; //右边部分第一个节点
        slow.next = null;
        Node n3 = slow; //循环后会指向最右一个节点
        Node n2 = null;
        while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1; // n3 移动
            n1 = n2; // n1 移动
        }


        //只要有一个不相等,就返回false
        boolean res = true;
        n1 = head;
        n2 = n3;
        while (n1 != null) {
            if (n1.value != n2.value) {
                res = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }

        //恢复原链表
        n1 = n3.next;
        n3.next = null;
        while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }

        return res;
    }
}
